package com.yangli.leecode.mashib.code;

/**
 * @Description
 * @Author liyang
 * @Date 2023/5/30 14:46
 */
public class Code_Manacher {
    public static void main(String[] args){

    }

    public static int Manacher(String str){
        if (str == null || str.length() == 0) {
            return -1;
        }
        char[] next = insertAssistChar(str);
        int[] radius = new int[str.length()];//每个位置上，存储的回文半径
        int R = -1;//已知回文最大右边界+1
        int C = -1;//已知回文最大右边界时中心点
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < str.length(); i++) {
            int minRadius = R > i ? Math.min(radius[2 * C - i], R - i) : 1;

            while (i+minRadius<str.length()&&i-minRadius>-1){
                if(str.charAt(i+minRadius)==str.charAt(i-minRadius)) {
                    minRadius++;
                }else {
                    break;
                }
            }
            radius[i] = minRadius;
            max = Math.max(max,minRadius);

        }
        return  max-1;//最大半径减一 就等于原始串的最大回文直径

    }

    public static char[] insertAssistChar(String str){
        char[] res = new char[str.length() * 2 + 1];
        for (int i = 0; i < res.length; i++) {
            if (i % 2 == 0) {
                res[i] = '#';
            } else {
                res[i] = str.charAt(i / 2);
            }
        }
        return res;
    }


}
